package 动态规划.背包问题;

/**
 * @description:
 * @author: ywk
 * @date: 2020-12-22
 */
public class 切分两子集 {
    static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int n = nums.length;
        sum = sum / 2;
        boolean[][] dp = new boolean[n + 1][sum + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        for (int i = 0; i <= sum; i++) {
            dp[0][i] = false;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (j - nums[i - 1] < 0) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] |
                            dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][sum];
    }

    static boolean[] visited = new boolean[256];

    static boolean canPartitionBackTrack(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum = sum / 2;
        return canPartition(nums, sum, 0);
    }

    private static boolean canPartition(int[] nums, int sum, int start) {
        boolean flag = false;
        if (sum == 0) {
            return true;
        }
        for (int i = start; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            flag |= canPartition(nums, sum - nums[i], start + 1);
            visited[i] = false;
        }
        return flag;
    }


    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 4, 2}));
        System.out.println(canPartitionBackTrack(new int[]{2, 2, 2, 4, 2}));
    }
}
